package history

/**
 * @Description: 中序遍历 使用栈
 * @Keyword:
 * @Author: kami
 * @Date: 2022/6/9 13:52
 **/
func findKthNode(root *Tree, k int) []int {
	var stack = []*Tree{root}
	var cnt = 1
	var res []int
	for len(stack) > 0 {
		size := len(stack)
		var last = stack[size-1]
		stack = stack[0 : size-1]
		cnt++
		if cnt == k {
			return res
		}
		if last.Right != nil {
			stack = append(stack, last.Right)
		}
		if last.Left != nil {
			stack = append(stack, last.Left)
		}
	}
	return nil
}

/*
栈 前序遍历
*/
func preSearch(root *Tree) []int {
	var stack = []*Tree{root}
	var res []int
	for len(stack) > 0 {
		size := len(stack)
		var last = stack[size-1]
		stack = stack[0 : size-1]
		res = append(res, last.Val)
		if last.Right != nil {
			stack = append(stack, last.Right)
		}
		if last.Left != nil {
			stack = append(stack, last.Left)
		}
	}
	return res
}

/*
栈 中序遍历
*/
func inSearch(root *Tree) []int {
	var stack = []*Tree{root}
	var res []int
	var searchNode = root.Left
	for len(stack) > 0 || searchNode != nil {
		// 先左节点
		if searchNode != nil {
			stack = append(stack, searchNode)
			searchNode = searchNode.Left
		} else {
			n := len(stack)
			searchNode = stack[n-1]
			stack = stack[0 : n-1]
			res = append(res, searchNode.Val)
			searchNode = searchNode.Right
		}
	}
	return res
}

/*
，使用栈保存遍历过的节点，先找到最右节点然后依次出栈遍历节点对应的左子节点，最后需要反转遍历结果
*/
func postSearch(root *Tree) []int {
	var stack = []*Tree{root}
	var res []int

	for len(stack) > 0 || root != nil {
		for root != nil {
			res = append(res, root.Val)
			stack = append(stack, root)
			root = root.Right
		}
		root = stack[len(stack)-1].Left
		stack = stack[0 : len(stack)-1]
	}
	var n = len(res)
	var half = n / 2
	for i := 0; i < half; i++ {
		res[i], res[n-i-1] = res[n-i-1], res[i]
	}
	return res
}

/**
 * @Description: 前序遍历 中左右
 * @Keyword:
 * @Author: kami
 * @Date: 2022/6/22 20:06
 **/
func preSearchStack(root *Tree) []int {
	var res []int
	var stack = []*Tree{root}

	for len(stack) > 0 {
		top := stack[len(stack)-1]
		stack = stack[0 : len(stack)-1]
		res = append(res, top.Val)
		if top.Right != nil {
			stack = append(stack, top.Right)
		}
		if top.Left != nil {
			stack = append(stack, top.Left)
		}
	}
	return res
}

/**
 * @Description: 后序遍历 中左右
 * @Keyword:
 * @Author: kami
 * @Date: 2022/6/22 20:06
 **/
func postSearchStack(root *Tree) []int {
	var res []int
	var stack = []*Tree{root}

	// 完成了中 右 左
	for len(stack) > 0 {
		top := stack[len(stack)-1]
		stack = stack[0 : len(stack)-1]
		res = append(res, top.Val)
		if top.Left != nil {
			stack = append(stack, top.Left)
		}
		if top.Right != nil {
			stack = append(stack, top.Right)
		}

	}
	// 中 右 左 逆序输出
	for i := 0; i < len(res)/2; i++ {
		res[i], res[len(res)-1-i] = res[len(res)-1-i], res[i]
	}
	return res
}

/**
 * @Description: 中序遍历 中左右
 * @Keyword: 遍历顺序和处理顺序不一致，需要借助额外的指针
 * @Author: kami
 * @Date: 2022/6/22 20:06
 **/
func midSearchStack(root *Tree) []int {
	var res []int
	if root == nil {
		return res
	}
	var stack = []*Tree{}
	var curNode = root
	// 完成了中 右 左
	for curNode != nil || len(stack) > 0 {
		if curNode != nil {
			stack = append(stack, curNode)
			curNode = curNode.Left
		} else {
			top := stack[len(stack)-1]
			res = append(res, top.Val)
			stack = stack[0 : len(stack)-1]
			curNode = top.Right
		}
	}
	return res
}
